﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace FrogEngine
{
	public class Graph<K, V> : IGraph<K, V>
	{
		public Graph()
		{
			nodes = new HashSet<IGraphVertex<K, V>>();
			edges = new List<IGraphEdge<K, V>>();
		}

		public Graph(string fileName)
		{
			nodes = new HashSet<IGraphVertex<K, V>>();
			edges = new List<IGraphEdge<K, V>>();
			LoadFromFile(fileName);
		}

		private HashSet<IGraphVertex<K, V>> nodes;
		public ISet<IGraphVertex<K, V>> Vertices
		{
			get { return nodes; }
		}

		private List<IGraphEdge<K, V>> edges;
		public IList<IGraphEdge<K, V>> Edges
		{
			get { return edges; }
		}

		public IGraphVertex<K, V> BFS(V value)
		{
			if (Vertices.Count == 0)
				return null;

			foreach (var vertex in Vertices)
			{
				vertex.Visited = false;
				vertex.Predecessor = null;
				vertex.PathCost = 0;
			}

			Queue<IGraphVertex<K, V>> Q = new Queue<IGraphVertex<K, V>>();
			Q.Enqueue(Vertices.ElementAt(0));
			while (Q.Count != 0)
			{
				var vert = Q.Dequeue();
				vert.Visited = true;
				foreach (var vertex in vert.AdjacentVertices)
				{
					if (!vertex.Visited)
					{
						if (Comparer<V>.Default.Compare(value, vertex.Value) == 0)
							return vertex;
						Q.Enqueue(vertex);
					}
				}
			}

			return null;
		}

		public IGraphVertex<K, V> BFS(K key)
		{
			if (Vertices.Count == 0)
				return null;

			foreach (var vertex in Vertices)
			{
				vertex.Visited = false;
				vertex.Predecessor = null;
				vertex.PathCost = 0;
			}

			Queue<IGraphVertex<K, V>> Q = new Queue<IGraphVertex<K, V>>();
			Q.Enqueue(Vertices.ElementAt(0));
			while (Q.Count != 0)
			{
				var vert = Q.Dequeue();
				vert.Visited = true;
				foreach (var vertex in vert.AdjacentVertices)
				{
					if (!vertex.Visited)
					{
						if (Comparer<K>.Default.Compare(key, vertex.Key) == 0)
							return vertex;
						Q.Enqueue(vertex);
					}
				}
			}

			return null;
		}

		public IGraphVertex<K, V> DFS(V value)
		{
			if (Vertices.Count == 0)
				return null;
			foreach (var vertex in Vertices)
			{
				vertex.Visited = false;
				vertex.Predecessor = null;
				vertex.PathCost = 0;
			}

			Stack<IGraphVertex<K, V>> Q = new Stack<IGraphVertex<K, V>>();
			Q.Push(Vertices.ElementAt(0));
			while (Q.Count != 0)
			{
				var vert = Q.Pop();
				if (Comparer<V>.Default.Compare(value, vert.Value) == 0)
					return vert;
				vert.Visited = true;
				foreach (var vertex in vert.AdjacentVertices)
					Q.Push(vertex);
			}

			return null;
		}

		public IGraphVertex<K, V> DFS(K key)
		{
			if (Vertices.Count == 0)
				return null;
			foreach (var vertex in Vertices)
			{
				vertex.Visited = false;
				vertex.Predecessor = null;
				vertex.PathCost = 0;
			}

			Stack<IGraphVertex<K, V>> Q = new Stack<IGraphVertex<K, V>>();
			Q.Push(Vertices.ElementAt(0));
			while (Q.Count != 0)
			{
				var vert = Q.Pop();
				if (Comparer<K>.Default.Compare(key, vert.Key) == 0)
					return vert;
				vert.Visited = true;
				foreach (var vertex in vert.AdjacentVertices)
					Q.Push(vertex);
			}

			return null;
		}

		public IEnumerable<IGraphVertex<K, V>> ShortestPath(IGraphVertex<K, V> start, IGraphVertex<K, V> end)
		{
			List<IGraphVertex<K, V>> path = new List<IGraphVertex<K, V>>();
			PriorityQueue<double, IGraphVertex<K, V>> Q = new PriorityQueue<double, IGraphVertex<K, V>>();
			for (int i = 0; i < nodes.Count; i++)
			{
				nodes.ElementAt(i).PathCost = 0;
				nodes.ElementAt(i).Visited = false;
				nodes.ElementAt(i).Predecessor = null;
				if (nodes.ElementAt(i) == start)
					Q.InsertItem(0, nodes.ElementAt(i));
				else
					Q.InsertItem(double.MaxValue, nodes.ElementAt(i));
			}

			while (!Q.IsEmpty)
			{
				var u = Q.MinElement;
				double key = Q.MinKey;
				Q.RemoveMin();
				u.PathCost = key;
				u.Visited = true;
				foreach (var vertex in u.AdjacentVertices)
				{
					if (!vertex.Visited)
					{
						var edge = u.GetSharedEdge(vertex);
						if (key + edge.Weight < Q.GetKey(vertex))
						{
							vertex.Predecessor = u;
							Q.ChangeKey(vertex, key + edge.Weight);
						}
					}
				}
			}

			var itNode = end;
			while (itNode.Predecessor != start)
				path.Add(itNode);
			path.Add(start);
			return path;
		}

		public IGraph<K, V> MinimumSpanningTree()
		{
			Graph<K, V> minTree = new Graph<K, V>();
			PriorityQueue<double, IGraphEdge<K, V>> Q = new PriorityQueue<double, IGraphEdge<K, V>>();
			Dictionary<IGraphVertex<K, V>, HashSet<IGraphVertex<K, V>>> C = new Dictionary<IGraphVertex<K, V>, HashSet<IGraphVertex<K, V>>>();
			foreach (var edge in Edges)
				Q.InsertItem(edge.Weight, edge);
			foreach (var vertex in Vertices)
			{
				var set = new HashSet<IGraphVertex<K, V>>();
				set.Add(vertex);
				C.Add(vertex, set);
			}
			List<IGraphEdge<K, V>> T = new List<IGraphEdge<K, V>>();
			
			while (T.Count < Vertices.Count - 1)
			{
				var edge = Q.MinElement;
				Q.RemoveMin();
				if (!C[edge.V1].SetEquals(C[edge.V2]))
				{
					T.Add(edge);
					var merged = C[edge.V1].Union(C[edge.V2]);
					C[edge.V1] = new HashSet<IGraphVertex<K,V>>(merged);
					C[edge.V2] = new HashSet<IGraphVertex<K,V>>(merged);
				}
			}
			foreach (var edge in T)
			{
				minTree.Vertices.Add(edge.V1);
				minTree.Vertices.Add(edge.V2);
				minTree.Edges.Add(edge);
			}
			return minTree;
		}

		public IEnumerable<IGraphVertex<K, V>> AStar(IGraphVertex<K, V> start, IGraphVertex<K, V> end, Heuristic<IGraphVertex<K, V>, double> H)
		{
			List<IGraphVertex<K, V>> path = new List<IGraphVertex<K, V>>();
			PriorityQueue<double, IGraphVertex<K, V>> Q = new PriorityQueue<double, IGraphVertex<K, V>>();
			Q.InsertItem(0, start);

			while (!Q.IsEmpty)
			{
				var node = Q.MinElement;
				var key = Q.MinKey;
				Q.RemoveMin();
				if (node.Visited)
					continue;
				node.Visited = true;
				node.PathCost = key;
				path.Add(node);
				if (node == end)
					return path;

				foreach (var vertex in node.AdjacentVertices)
				{
					double d = node.GetSharedEdge(vertex).Weight;
					Q.InsertItem(path[path.Count - 1].PathCost + H.Eval(vertex, end), vertex);
				}
			}

			return path;
		}

		public virtual void LoadFromFile(string fileName)
		{

		}
	}
}
